package com.bee.剑指offer;

import java.math.BigInteger;
import java.util.*;

/**
 * 输入一个正整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 * 例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。
 */
public class 把数组排成最小的数 {

    private static Stack<Integer> stack = new Stack<>();

    private static List<List<BigInteger>> result = new ArrayList<>();

    private static BigInteger min = new BigInteger("0");

    public String PrintMinNumber(int[] numbers) {
        if (numbers.length == 0) {
            return "";
        }
        f(numbers, numbers.length, 0);
        return String.valueOf(min);
    }

    /**
     * 这种排列性能会有问题
     */
    public static void f(int[] array, int target, int cur) {
        // 需要选择的数据和当前已经选择的数据已经相等了，可以退出
        if (target == cur) {
            // 在这里是一次组合之后的数据，可以写到数组中，或者判断大小
            List<Integer> list = stack.subList(0, stack.size());
            List<Integer> aa = new ArrayList<>(list);
            StringBuilder str = new StringBuilder();
            for (int i = 0; i < aa.size(); i++) {
                str.append(aa.get(i));
            }
            if (min.equals(new BigInteger("0"))) {
                min = new BigInteger(str.toString());
            }
            min = min.min(new BigInteger(str.toString()));
            System.out.println(min);
            return;
        }
        for (int i = 0; i < array.length; i++) {
            if (stack.contains(array[i])) {
                continue;
            }
            stack.add(array[i]);
            f(array, target, cur + 1);
            stack.pop();
        }
    }

    public String PrintMinNumber2(int[] numbers) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < numbers.length; i++) {
            list.add(Integer.valueOf(numbers[i]));
        }
        // 使用自定义的排序器进行排序
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                String s1 = String.valueOf(a);
                String s2 = String.valueOf(b);
                // A < B 将s1放在前面
                String A = s1 + s2;
                String B = s2 + s1;
                return A.compareTo(B);
            }
        });
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            stringBuilder.append(list.get(i));
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        BigInteger big = new BigInteger("333433333332");
        System.out.println(big.toString());
    }
}
